Національний університет “Львівська політехніка” Кафедра ЕОМ Курсова робота ( частина 2 ) На тему: “ Динамічні структури даних ” з дисципліни: " Програмування" Вибір варіантів індивідуального завдання: Вибір АТД: № = [(16) + (1994) + (117) ] % 4 + 1 = 4 Примітка: 1 – стек, 2 – черга, 3- список, 4 – дерево. Вибір номера завдання: № = [(4) + (1994) + (83) ] % 10 + 1 = 2  ЗАВДАННЯ НА КУРСОВУ РОБОТУ Побудувати бінарне дерево пошуку для послідовності чисел, що вводяться з клавіатури. Реалізувати операції додавання та вилучення вузлів з бінарного дерева пошуку. Виконати обхід дерева у заданому порядку та показати: послідовність вершин дерева при проходженні його у прямому порядку; послідовність листків дерева при проходженні його у зворотньому порядку; послідовність вузлів, що мають тільки одного нащадка при проходженні дерева у симетричному порядку. Вилучити з дерева всi листки. 2) Глосарій або предметний покажчик підручника складається з впорядкованих по алфавіту основних термінів, кожен з яких супроводжується впорядкованою за зростанням послідовністю номерів сторінок, де він зустрічається, і множиною підтермінів. Підтерміни виводяться на наступних за основним терміном рядках, вони дещо зсунуті вправо відносно основного терміна і впорядковані по алфавіту всередині основного терміна. Кожен підтермін супроводжується впорядкованою за зростанням послідовністю номерів сторінок, де він зустрічається. Розробити структуру даних для представлення такого предметного покажчика і написати програму для зображення предметного покажчика по вхідних даних, що зберігаються у текстовому файлі. Кожний вхідний рядок починається або з символу М (основний термін), або з символу S (підтермін). Рядок з символом М містить основний термін, за котрим слідують номери сторінок, на котрих зустрічається основний термін. Рядок з символом S будується аналогічно, за винятком того, що він містить не основний термін, а підтермін. Вхідні рядки з’являються у будь-якому порядку. Єдина умова: кожен підтермін вважається підтерміном найближчого попереднього основного терміна. Для одного основного терміна або підтерміна може бути декілька вхідних рядків (всі номери сторінок, що з’являються для конкретного терміна у будь-якому рядку, повинні бути надруковані разом з цим терміном). Зміст 1. Теоретична частина 4 2.Завдання 3. Побудова АТД 6 2.1. Постановка задачі 6 2.2. Динаміка вмісту 7 2.3. Результати виконання програми 10 3. Завдання 4. Застосування АТД 11 3.1. Постановка задачі 11 3.2. Алгоритм розв’язання задачі 12 3.2.1. Словесний опис алгоритму 12 3.2.2. Граф-схема алгоритму 12 3.3. Результати виконання програми 15 Висновки 16 Список літератури 17 Додаток А. Текст програми до завдання 3 18 Додаток Б. Текст програми до завдання 4 22  1. Теоретична частина Переваги динамічних структур даних Динамічні структури даних, щодо визначення, характеризуються відсутністю фізичної суміжності елементів структури пам'яті, непостійністю і непередбачуваністю розміру структури в процесі її обробки. Оскільки елементи динамічної структури розташовуються по непередбачуваним адресами пам'яті, адреса елемента такої структури не може бути обчислений з адреси початкового або попереднього елемента. Для встановлення зв'язку між елементами динамічної структури використовуються покажчики, через які встановлюються явні зв'язки між елементами. Таке подання даних у пам'яті називається зв'язковим. Елемент динамічної структури складається з двох полів: інформаційного поля або поля даних, в якому містяться ті дані, заради яких і створюється структура; в загальному випадку інформаційне поле саме є інтегрованою структурою-вектором, масивом, записом і т.п.; полі зв'язок...